package leetcode.stack_queue;

import java.util.ArrayDeque;

public class Lc649 {

    public String predictPartyVictory(String senate) {
        ArrayDeque<Integer> R = new ArrayDeque<>(); //记录存活的R下标
        ArrayDeque<Integer> D = new ArrayDeque<>();
        char[] chars = senate.toCharArray();
        int preRCnt = 0, preDCnt = 0;
        while (true) {
            for (int i = 0; i < chars.length; i++) {
                char c = chars[i];
                if (c == 'R') {
                    if (preDCnt > 0) {
                        preDCnt--;
                        chars[i] = '-'; //前面R 投票干掉D
                    } else {
                        preRCnt++; //留着等干掉后面的D
                        R.offerLast(i); //保留当前R的下标
                    }
                } else if (c == 'D') {
                    if (preRCnt > 0) {
                        chars[i] = '-'; //当前D被前面的R干掉
                        preRCnt--;
                    } else {
                        preDCnt++;
                        D.offerLast(i);
                    }
                }
            }
            while (preRCnt > 0 && !D.isEmpty()) { //还有权力没用完的继续用完
                int idx = D.pollFirst();
                chars[idx] = '-';
                preRCnt--;
            }
            while (preDCnt > 0 && !R.isEmpty()) {
                preDCnt--;
                int idx = R.pollFirst();
                chars[idx] = 'x';
            }
            String temp = String.valueOf(chars);
            if (!temp.contains("R") || !temp.contains("D")) break;
        }
        String temp = String.valueOf(chars);
        return temp.contains("R") ? "Radiant" : "Dire";
    }

    public static void main(String[] args) {

        Lc649 lc649 = new Lc649();
        System.out.println(lc649.predictPartyVictory("RRDDD"));


    }
}
